#include<iostream>
#include<queue>

using namespace std;

typedef struct node{
    int value;
    struct node* lChild;
    struct node* rChild;
}Node;

// 二叉树的实现
class binaryTree
{
    public:

        binaryTree()
        {
            root=new Node;
            root->value=0;
            root->lChild=NULL;
            root->rChild=NULL;
        }
        binaryTree(int value)
        {
            root=new Node;
            root->value=value;
            root->lChild=NULL;
            root->rChild=NULL;
        }

        void buildTree(int *array,int arrayLen);
        void buildTree2(int *array,int arrayLen);
        void buildTree3(int *array,int arrayLen);
        int& getEmptyNode();
        void inorderSearch(Node* n);
        void preorderSearch(Node* n);
        void postorderSearch(Node* n);
        void levelSearch(Node* n);

        void deleteLastNode();

        void addNodeInLast(int);

        // 修改层序遍历搜索到的第一个值
        bool changeFirstNode(int,int);

        int getHigh();
        int getLength();
        Node* getRoot();

    private:
        Node *root;
        int treeHigh;
        int nodeLength;
        void getHigh(int,Node*);
};

Node* binaryTree::getRoot()
{
    return this->root;
}

void binaryTree::inorderSearch(Node* n)
{
    if(n->lChild!=NULL&&n->lChild->value!=-1)
    {
        inorderSearch(n->lChild);
    }
    cout<<n->value<<"  ";
    if(n->rChild!=NULL&&n->rChild->value!=-1)
    {
        inorderSearch(n->rChild);
    }
}

void binaryTree::preorderSearch(Node* n)
{
    cout<<n->value<<"  ";
    if(n->lChild!=NULL&&n->lChild->value!=-1)
    {
        inorderSearch(n->lChild);
    }
    if(n->rChild!=NULL&&n->rChild->value!=-1)
    {
        inorderSearch(n->rChild);
    }
}

void binaryTree::postorderSearch(Node* n)
{
    if(n->lChild!=NULL&&n->lChild->value!=-1)
    {
        inorderSearch(n->lChild);
    }
    if(n->rChild!=NULL&&n->rChild->value!=-1)
    {
        inorderSearch(n->rChild);
    }
    cout<<n->value<<"  ";
}

void binaryTree::levelSearch(Node *n)
{
    queue<Node*> q;
    Node* tempNode;
    q.push(n);
    while(!q.empty())
    {
        tempNode=q.front();
        q.pop();
        cout<<tempNode->value<<"  ";
        if(tempNode->lChild!=NULL && tempNode->lChild->value!=-1)
        {
            q.push(tempNode->lChild);
        }
        if(tempNode->rChild!=NULL && tempNode->rChild->value!=-1)
        {
            q.push(tempNode->rChild);
        }
    }
}

int& binaryTree::getEmptyNode()
{
    Node* n=this->root;
    queue<Node*> q;
    q.push(n);
    Node* tempNodes[20];
    int length=0;
    while(!q.empty())
    {
        n=q.front();
        tempNodes[length]=n;
        length++;
        q.pop();
        if(n->value==-1)
        {
            return n->value;
        }
        if(n->lChild!=NULL)
        {
            q.push(n->lChild);
        }
        if(n->rChild!=NULL)
        {
            q.push(n->rChild);
        }
    }

}

void binaryTree::buildTree(int* array,int arrayLen)
{
    Node* n=this->root;
    queue<Node*> Q;
    Q.push(this->root);
    int tempIndex=0;
    for(int i=0;i<arrayLen;i++)
    {
        n=Q.front();
        n->value=array[i];
        Q.pop();
        if(n->lChild==NULL)
        {
            n->lChild=new Node;
            n->lChild->value=-1;
            n->lChild->lChild=NULL;
            n->lChild->rChild=NULL;
        }
        if(n->rChild==NULL)
        {
            n->rChild=new Node;
            n->rChild->value=-1;
            n->rChild->lChild=NULL;
            n->rChild->rChild=NULL;
        }

        Q.push(n->lChild);
        Q.push(n->rChild);
    }
}

void binaryTree::buildTree2(int* array,int arrayLen)
{
    Node* n=this->root;
    int i=0,j=1;
    Node** nodeArray=new Node*[arrayLen];
    nodeArray[0]=this->root;
    while(j<arrayLen)
    {
        nodeArray[i]->lChild=new Node;
        nodeArray[i]->lChild->lChild=NULL;
        nodeArray[i]->lChild->rChild=NULL;
        nodeArray[j]=nodeArray[i]->lChild;
        j++;
        if(j>=arrayLen)
        {
            break;
        }
        nodeArray[i]->rChild=new Node;
        nodeArray[i]->rChild->lChild=NULL;
        nodeArray[i]->rChild->rChild=NULL;
        nodeArray[j]=nodeArray[i]->rChild;
        j++;
        i++;
    }
    for(int i=0;i<arrayLen;i++)
    {
        nodeArray[i]->value=array[i];
    }
}

void binaryTree::buildTree3(int* array,int arrayLen)
{
    queue<Node*> q;
    q.push(this->root);
    Node* n;
    int tempIndex=1;
    while(tempIndex<arrayLen)
    {
        n=q.front();
        q.pop();
        n->value=-1;
        n->lChild=new Node;
        n->lChild->value=-1;
        n->lChild->lChild=NULL;
        n->lChild->rChild=NULL;
        q.push(n->lChild);
        tempIndex++;
        if(tempIndex>=arrayLen)
        {
            break;
        }
        n->rChild=new Node;
        n->rChild->value=-1;
        n->rChild->lChild=NULL;
        n->rChild->rChild=NULL;
        q.push(n->rChild);
        tempIndex++;
    }
    for(int i=0;i<arrayLen;i++)
    {
        this->getEmptyNode()=array[i];
    }
    
}

int binaryTree::getHigh()
{
    int reHigh=0;
    this->treeHigh=0;
    this->getHigh(1,this->root);
    return this->treeHigh;
}

void binaryTree::getHigh(int H,Node* n)
{
    if(H>this->treeHigh)
    { 
        this->treeHigh=H;
    }
    if(n->lChild!=NULL)
    {
        getHigh(H+1,n->lChild);
    }
    if(n->rChild!=NULL)
    {
        getHigh(H+1,n->rChild);
    }
}

int binaryTree::getLength()
{
    int reValue=0;
    Node* n;
    queue<Node*> q;
    q.push(this->root);
    while(!q.empty())
    {
        n=q.front();
        q.pop();
        reValue++;
        if(n->lChild!=NULL && n->lChild->value!=-1)
        {
            q.push(n->lChild);
        }
        if(n->rChild!=NULL && n->rChild->value!=-1)
        {
            q.push(n->rChild);
        }
    }
    this->nodeLength=reValue;
    return reValue;
}

void binaryTree::deleteLastNode()
{
    Node** n=new Node*[this->nodeLength];
    int tempIndex=0;
    queue<Node*> q;
    q.push(this->root);
    Node* tempNode;
    while(!q.empty())
    {
        tempNode=q.front();
        q.pop();
        n[tempIndex++]=tempNode;
        if(tempNode->lChild!=NULL && tempNode->lChild->value!=-1)
        {
            q.push(tempNode->lChild);
        }
        if(tempNode->rChild!=NULL && tempNode->rChild->value!=-1)
        {
            q.push(tempNode->rChild);
        }
    }
    int lastNodeIndex=this->getLength()-1;
    if(lastNodeIndex%2!=0)
    {
        cout<<n[(lastNodeIndex-1)/2]->lChild->value<<endl;
        n[(lastNodeIndex-1)/2]->lChild=NULL;
    }
    else
    {
        n[(lastNodeIndex-2)/2]->rChild=NULL;
    }
    delete n[lastNodeIndex];
    this->getLength();
}

void binaryTree::addNodeInLast(int value)
{
    this->getLength();
    queue<Node*> q;
    Node* tempNode;
    int tempIndex=0;
    q.push(this->getRoot());
    Node** nodeList=new Node*[this->nodeLength+1];
    while(!q.empty())
    {
        tempNode=q.front();
        q.pop();
        nodeList[tempIndex++]=tempNode;
        if(tempNode->lChild!=NULL && tempNode->lChild->value!=-1)
        {
            q.push(tempNode->lChild);
        }
        if(tempNode->rChild!=NULL && tempNode->rChild->value!=-1)
        {
            q.push(tempNode->rChild);
        }
    }
    if(nodeLength%2==0)
    {
        nodeList[(nodeLength-2)/2]->rChild=new Node;
        nodeList[(nodeLength-2)/2]->rChild->value=value;
        nodeList[(nodeLength-2)/2]->rChild->lChild=NULL;
        nodeList[(nodeLength-2)/2]->rChild->rChild=NULL;
    }
    else
    {
        nodeList[(nodeLength-1)/2]->lChild=new Node;
        nodeList[(nodeLength-1)/2]->lChild->value=value;
        nodeList[(nodeLength-1)/2]->lChild->lChild=NULL;
        nodeList[(nodeLength-1)/2]->lChild->rChild=NULL;
    }
}

bool binaryTree::changeFirstNode(int searchValue,int changeValue)
{
    Node* tempNode=this->root;
    queue<Node*> q;
    q.push(this->root);
    while(!q.empty())
    {
        tempNode=q.front();
        q.pop();
        if(tempNode->value==searchValue)
        {
            tempNode->value=changeValue;
            return true;
        }
        if(tempNode->lChild!=NULL)
        {
            q.push(tempNode->lChild);
        }
        if(tempNode->rChild!=NULL)
        {
            q.push(tempNode->rChild);
        }
    }

    return false;
}

int& test(int array[])
{
    return array[2];
}

int main()
{
    int arr[10]={12,13,1,2,3,4,5};
    binaryTree tree;
    tree.buildTree(arr,7);
    tree.inorderSearch(tree.getRoot());

    cout<<endl;

    binaryTree tree2;
    tree2.buildTree2(arr,7);
    tree2.inorderSearch(tree2.getRoot());

    cout<<endl;
    tree2.preorderSearch(tree2.getRoot());

    cout<<endl;
    tree2.postorderSearch(tree2.getRoot());

    cout<<endl;
    tree2.levelSearch(tree2.getRoot());

    cout<<"\n------------"<<endl;

    binaryTree tree3;
    arr[7]=21;
    tree3.buildTree3(arr,8);
    tree3.inorderSearch(tree3.getRoot());

    cout<<endl;
    cout<<tree3.getHigh()<<endl;

    int arr2[3]={12,11,10};
    binaryTree tree4;
    tree4.buildTree2(arr2,3);
    tree4.levelSearch(tree4.getRoot());
    cout<<'\n'<<tree4.getHigh()<<endl;
    cout<<tree4.getLength()<<endl;

    tree3.levelSearch(tree3.getRoot());
    cout<<endl;
    // cout<<tree3.levelSearch()<<endl;
    cout<<tree2.getLength()<<endl;
    tree3.getLength();
    tree3.deleteLastNode();
    tree3.deleteLastNode();
    tree3.levelSearch(tree3.getRoot());

    tree3.addNodeInLast(50);
    tree3.addNodeInLast(51);

    cout<<endl;
    tree3.levelSearch(tree3.getRoot());

    tree3.changeFirstNode(1,22);

    cout<<endl;
    tree3.levelSearch(tree3.getRoot());
}   

